λ¬Έμ
IT λ²€μ² νμ¬λ₯Ό μ΄μνκ³ μλ λΌμ΄μΈμ λ§€λ μ¬λ΄ ν΄μ»€ν€ λνλ₯Ό κ°μ΅νμ¬ μ°μΉμμκ² μκΈμ μ§κΈνκ³ μμ΅λλ€. μ΄λ² λνμμλ μ°μΉμμκ² μ§κΈλλ μκΈμ μ΄μ λνμλ λ€λ₯΄κ² λ€μκ³Ό κ°μ λ°©μμΌλ‘ κ²°μ νλ €κ³ ν©λλ€. ν΄μ»€ν€ λνμ μ°Έκ°νλ λͺ¨λ μ°Έκ°μλ€μκ²λ μ«μλ€κ³Ό 3κ°μ§μ μ°μ°λ¬Έμ(+, -, ) λ§μΌλ‘ μ΄λ£¨μ΄μ§ μ°μ° μμμ΄ μ λ¬λλ©°, μ°Έκ°μμ λ―Έμ μ μ λ¬λ°μ μμμ ν¬ν¨λ μ°μ°μμ μ°μ μμλ₯Ό μμ λ‘κ² μ¬μ μνμ¬ λ§λ€ μ μλ κ°μ₯ ν° μ«μλ₯Ό μ μΆνλ κ²μ λλ€. λ¨, μ°μ°μμ μ°μ μμλ₯Ό μλ‘ μ μν λ, κ°μ μμμ μ°μ°μλ μμ΄μΌ ν©λλ€. μ¦, + > - > * λλ - > * > + λ±κ³Ό κ°μ΄ μ°μ°μ μ°μ μμλ₯Ό μ μν μ μμΌλ +, > - λλ * > +,-μ²λΌ 2κ° μ΄μμ μ°μ°μκ° λμΌν μμλ₯Ό κ°μ§λλ‘ μ°μ°μ μ°μ μμλ₯Ό μ μν μλ μμ΅λλ€. μμμ ν¬ν¨λ μ°μ°μκ° 2κ°λΌλ©΄ μ μν μ μλ μ°μ°μ μ°μ μμ μ‘°ν©μ 2! = 2κ°μ§μ΄λ©°, μ°μ°μκ° 3κ°λΌλ©΄ 3! = 6κ°μ§ μ‘°ν©μ΄ κ°λ₯ν©λλ€. λ§μ½ κ³μ°λ κ²°κ³Όκ° μμλΌλ©΄ ν΄λΉ μ«μμ μ λκ°μΌλ‘ λ³ννμ¬ μ μΆνλ©° μ μΆν μ«μκ° κ°μ₯ ν° μ°Έκ°μλ₯Ό μ°μΉμλ‘ μ μ νλ©°, μ°μΉμκ° μ μΆν μ«μλ₯Ό μ°μΉμκΈμΌλ‘ μ§κΈνκ² λ©λλ€.
μλ₯Ό λ€μ΄, μ°Έκ°μ μ€ λ€μ€κ° μλμ κ°μ μμμ μ λ¬λ°μλ€κ³ κ°μ ν©λλ€.
"100-200*300-500+20"
μΌλ°μ μΌλ‘ μν λ° μ μ°νμμ μ½μλ μ°μ°μ μ°μ μμμ λ°λ₯΄λ©΄ λνκΈ°μ λΉΌκΈ°λ μλ‘ λλ±νλ©° κ³±νκΈ°λ λνκΈ°, λΉΌκΈ°μ λΉν΄ μ°μ μμκ° λμ * > +,- λ‘ μ°μ μμκ° μ μλμ΄ μμ΅λλ€. λν κ·μΉμ λ°λΌ + > - > * λλ - > * > + λ±κ³Ό κ°μ΄ μ°μ°μ μ°μ μμλ₯Ό μ μν μ μμΌλ +,* > - λλ * > +,- μ²λΌ 2κ° μ΄μμ μ°μ°μκ° λμΌν μμλ₯Ό κ°μ§λλ‘ μ°μ°μ μ°μ μμλ₯Ό μ μν μλ μμ΅λλ€. μμμ μ°μ°μκ° 3κ° μ£Όμ΄μ‘μΌλ―λ‘ κ°λ₯ν μ°μ°μ μ°μ μμ μ‘°ν©μ 3! = 6κ°μ§μ΄λ©°, κ·Έ μ€ + > - > * λ‘ μ°μ°μ μ°μ μμλ₯Ό μ νλ€λ©΄ κ²°κ΄κ°μ 22,000μμ΄ λ©λλ€. λ°λ©΄μ * > + > - λ‘ μ°μ°μ μ°μ μμλ₯Ό μ νλ€λ©΄ μμμ κ²°κ΄κ°μ -60,420 μ΄μ§λ§, κ·μΉμ λ°λΌ μ°μΉ μ μκΈμ μ λκ°μΈ 60,420μμ΄ λ©λλ€.
μ°Έκ°μμκ² μ£Όμ΄μ§ μ°μ° μμμ΄ λ΄κΈ΄ λ¬Έμμ΄ expressionμ΄ λ§€κ°λ³μλ‘ μ£Όμ΄μ§ λ, μ°μΉ μ λ°μ μ μλ κ°μ₯ ν° μκΈ κΈμ‘μ return νλλ‘ solution ν¨μλ₯Ό μμ±ν΄μ£ΌμΈμ.
μ νμ¬ν
- expressionμ κΈΈμ΄κ° 3 μ΄μ 100 μ΄νμΈ λ¬Έμμ΄μ λλ€.
-
expressionμ 곡백문μ, κ΄νΈλ¬Έμ μμ΄ μ€λ‘μ§ μ«μμ 3κ°μ§μ μ°μ°μ(+, -, *) λ§μΌλ‘ μ΄λ£¨μ΄μ§ μ¬λ°λ₯Έ μ€μνκΈ°λ²(μ°μ°μ λ λμ μ¬μ΄μ μ°μ°κΈ°νΈλ₯Ό μ¬μ©νλ λ°©μ)μΌλ‘ ννλ μ°μ°μμ λλ€. μλͺ»λ μ°μ°μμ μ λ ₯μΌλ‘ μ£Όμ΄μ§μ§ μμ΅λλ€.
- μ¦, "402+-561*"μ²λΌ μλͺ»λ μμμ μ¬λ°λ₯Έ μ€μνκΈ°λ²μ΄ μλλ―λ‘ μ£Όμ΄μ§μ§ μμ΅λλ€.
-
expressionμ νΌμ°μ°μ(operand)λ 0 μ΄μ 999 μ΄νμ μ«μμ λλ€.
- μ¦, "100-2145*458+12"μ²λΌ 999λ₯Ό μ΄κ³Όνλ νΌμ°μ°μκ° ν¬ν¨λ μμμ μ λ ₯μΌλ‘ μ£Όμ΄μ§μ§ μμ΅λλ€.
- "-56+100"μ²λΌ νΌμ°μ°μκ° μμμΈ μμλ μ λ ₯μΌλ‘ μ£Όμ΄μ§μ§ μμ΅λλ€.
- expressionμ μ μ΄λ 1κ° μ΄μμ μ°μ°μλ₯Ό ν¬ν¨νκ³ μμ΅λλ€.
- μ°μ°μ μ°μ μμλ₯Ό μ΄λ»κ² μ μ©νλλΌλ, expressionμ μ€κ° κ³μ°κ°κ³Ό μ΅μ’ κ²°κ΄κ°μ μ λκ°μ΄ 263 - 1 μ΄νκ° λλλ‘ μ λ ₯μ΄ μ£Όμ΄μ§λλ€.
- κ°μ μ°μ°μλΌλ¦¬λ μμ μλ κ²μ μ°μ μμκ° λ λμ΅λλ€.
μ μΆλ ₯ μ
| expression | return | |
|---|---|---|
| "100-200*300-500+20" | 60420 | |
| "50*6-3*2" | 300 |
π Logic
private void compute(int n) {
ArrayList<Long> numbers = new ArrayList<>(nums);
StringBuilder tmpOps = new StringBuilder(operands);
for (char p : perm) {
int idx = tmpOps.indexOf(String.valueOf(p));
while(idx != -1) {
long n1 = numbers.get(idx);
long n2 = numbers.get(idx+1);
numbers.set(idx, calculator(n1,n2,p));
numbers.remove(idx+1);
tmpOps.deleteCharAt(idx);
idx = tmpOps.indexOf(String.valueOf(p));
}
}
long sum = Math.abs(numbers.get(0));
if (answer < sum) answer = sum;
}
-
μμμ μ«μλ€μ μ μ₯νκ³ μλ
numsμ 볡μ¬νnumbersμ μ°μ°μλ€μ μμλλ‘ μ μ₯νλoperandsλ₯Ό 볡μ¬νtmpOpsλ₯Ό μ¬μ©νλ€.- μ΄ν κ³μ° μ μ«μμ μ°μ°μλ₯Ό λ°°μ΄μμ μμ νκΈ° μν΄ μμ μ μ₯μλ₯Ό μ¬μ©νλ€.
- μ°μ μμλλ‘ μ°μ°μλ₯Ό μ μ₯ν
permμ νμνλ©΄μ, ν΄λΉ μ°μ°μμ μμΉλ₯Ό κΈ°μ€μΌλ‘ μ«μλ€μ κ³μ°νκ³ , λμΉν ν, μμ νλ€.
π CODE
μ½λ 보기/μ κΈ°π«
import java.util.*;
class Solution {
long answer = 0;
ArrayList<Long> nums = new ArrayList<>();
ArrayList<Character> perm = new ArrayList<>();
StringBuilder operands = new StringBuilder();
public long solution(String expression) {
StringBuilder tmp = new StringBuilder();
for (int i = 0; i < expression.length(); i++) {
char ch = expression.charAt(i);
if (48 <= ch && ch <= 57) tmp.append(ch);
else {
nums.add((long) Integer.parseInt(String.valueOf(tmp)));
if (!perm.contains(ch)) perm.add(ch);
operands.append(ch);
tmp.delete(0, tmp.length());
}
}
nums.add((long) Integer.parseInt(String.valueOf(tmp)));
// μμ΄ μμ±
makePerm(0, perm.size(), perm.size());
return answer;
}
private void makePerm(int depth, int n, int r) {
if (depth == r) {
compute(n);
return;
}
for (int i = depth; i < n; i++) {
Collections.swap(perm, depth, i);
makePerm(depth + 1, n, r);
Collections.swap(perm, depth, i);
}
}
private void compute(int n) {
ArrayList<Long> numbers = new ArrayList<>(nums);
// μ°μ°μ μμ λ°°μ΄μ΄ νμ
// stringμ κ° λ¬Έμλ³ μμΉ μ‘°νκ° κ°λ₯νμ§λ§, μμ μμ κ° μλ¨
// arrayListλ μμ μμ κ° μ©μ΄νμ§λ§, μμΉ μ‘°νκ° μλ¨
StringBuilder tmpOps = new StringBuilder(operands);
for (char p : perm) {
int idx = tmpOps.indexOf(String.valueOf(p));
while(idx != -1) {
long n1 = numbers.get(idx);
long n2 = numbers.get(idx+1);
numbers.set(idx, calculator(n1,n2,p));
numbers.remove(idx+1);
tmpOps.deleteCharAt(idx);
idx = tmpOps.indexOf(String.valueOf(p));
}
}
long sum = Math.abs(numbers.get(0));
if (answer < sum) answer = sum;
}
private long calculator(long n1, long n2, char op) {
return switch (op) {
case '-' -> n1 - n2;
case '+' -> n1 + n2;
case '*' -> n1 * n2;
default -> 0;
};
}
}
βοΈ Review
- μ°μ°μμ λν μμ΄μ΄ νμνλ€λ μ μ μ½κ² μμμ§λ§, μ΄ν κ³μ°μ ꡬννλλ° μκ°μ λ무 λ§μ΄ μΌλ€.
- μμ§ μλ°μ λν 곡λΆκ° λ νμν κ² κ°λ€. (
String,StringBuilder,ArrayList<String>μμ μ¬μ©νλ λ©μλ)
π μΆμ²
Programmers : https://programmers.co.kr/learn/courses/30/lessons/67257